#include <iostream>
#include <vector>
using namespace std;

// 买卖一次
class maxProfit1 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int curMin = prices[0];
        int res = 0;

        for (int i = 1; i < n; i++) {
            // 每次都用当前售卖价格减去之前的最低价格
            curMin = min(curMin, prices[i]);
            res = max(res, prices[i] - curMin);
        }

        return res;
    }
};

// 买卖多次获得最大利润(不限次数)
class maxProfit2 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1];
        memset(dp, 0, sizeof(dp));

        // 动态规划
        for (int buy = n - 1; buy >= 0; buy--) {
            int res = 0;
            int curMin = prices[buy];
            for (int sell = buy + 1; sell < n; sell++) {
                curMin = min(curMin, prices[sell]);
                // dp[i]表示第i天买所得最大利润
                res = max(res, dp[sell + 1] + prices[sell] - curMin);
            }
            dp[buy] = res;
        }

        return dp[0];
    }
};

// 买卖多次获得最大利润(限次数)
class maxProfit3 {
public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
        int dp[n + 1][k + 1];
        memset(dp, 0, sizeof(dp));

        // 动态规划
        for (int i = 1; i <= k; i++) {
            for (int buy = n - 1; buy >= 0; buy--) {
                int res = 0;
                int curMin = prices[buy];
                for (int sell = buy + 1; sell < n; sell++) {
                    curMin = min(curMin, prices[sell]);
                    // dp[i]表示第i天买所得最大利润
                    res = max(res, dp[sell + 1][i - 1] + prices[sell] - curMin);
                }
                dp[buy][i] = res;
            }
        }

        return dp[0][k];
    }
};


// 状态机优化
class statusMaxProfitK {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][k + 1][2];
        memset(dp, 0, sizeof(dp));

        dp[0][k][0] = 0;
        dp[0][k][1] = INT_MIN;
        for (int i = 0; i <= n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = INT_MIN;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = k; j >= 1; j--) {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j][0] - prices[i - 1]);
            }
        }

        return dp[n][k][0];
    }
};

// k = 1
class statusMaxProfit1 {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][2];

        dp[0][1] = -prices[0];
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = max(dp[i - 1][1], - prices[i - 1]);
        }

        /* 空间优化版
        int dp_1 = -prices[0];
        int dp_0 = 0;

        for (int i = 1; i <= n; i++) {
            dp_0 = max(dp_0, dp_1 + prices[i - 1]);
            dp_1 = max(dp_1, - prices[i - 1]);
        }

        return dp_0;
        */

        return dp[n][0];
    }
};

// k = +infinity
class statusMaxProfitInf {
public:
    int maxProfitInf(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][2];

        dp[0][1] = -prices[0];
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]- prices[i - 1]);
        }

        /* 空间优化版
        int dp_1 = -prices[0];
        int dp_0 = 0;

        for (int i = 1; i <= n; i++) {
            int dp_0_temp = dp_0;
            dp_0 = max(dp_0, dp_1 + prices[i - 1]);
            dp_1 = max(dp_1, dp_0_temp - prices[i - 1]);
        }

        return dp_0;
        */

        return dp[n][0];
    }
};

// k = 2
class statusMaxProfit2 {
public:
    int maxProfit2(vector<int>& prices) {
        int n = prices.size();
        int dp[n + 1][3][2];

        // 初始化
        dp[0][1][1] = -prices[0];   // 只能买入卖出同一支股票
        dp[0][1][0] = 0;
        dp[0][2][1] = -prices[0];
        dp[0][2][0] = 0;

        for (int i = 1; i <= n; i++) {
            // dp[i][k][0]: 0-第i天，可交易k次，最终不持有股票的最大收入
            // dp[i][k][1]: 0-第i天，可交易k次，最终持有股票的最大收入
            // dp[i][2][1] = max(dp[i - 1][2][1] (rest), dp[i - 1][1][0] - prices[i - 1] (buy new stock 约定此时k--))
            dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i - 1]);
            dp[i][1][1] = max(dp[i - 1][1][1], /* dp[i - 1][0][0] = 0 */- prices[i - 1]);
            dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i - 1]);
            dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i - 1]);
        }

        /* 空间优化版
        int dp_i11 = -prices[0];
        int dp_i10 = 0;
        int dp_i21 = -prices[0];
        int dp_i20 = 0;

        for (int i = 1; i <= n; i++) {
            int temp = dp_i10;
            dp_i10 = max(dp_i10, dp_i11 + prices[i - 1]);
            dp_i11 = max(dp_i11, -prices[i - 1]);
            dp_i20 = max(dp_i20, dp_i21 + prices[i - 1]);
            dp_i21 = max(dp_i21, temp - prices[i - 1]);
        }

        return dp_i20;
        */

        return dp[n][2][0];
    }
};

// k = any interger
class statusMaxProfitN{
public:
    int maxProfitN(int k, vector<int>& prices) {
        if (prices.empty())
            return 0;
        int n = prices.size();
        if (k >= n / 2) {
            int dp0 = 0, dp1 = -prices[0];
            for (int i = 1; i < n; i++) {
                int temp = dp0;
                dp0 = max(dp0, dp1 + prices[i]);
                dp1 = max(dp1, temp - prices[i]);
            }
            return dp0;
        }
        // dp[i][j][0]: 0-i天，可交易j次，不持股最大收入
        // dp[i][j][1]: 0-i天，可交易j次，持股最大收入
        int dp[n][k + 1][2];
        memset(dp, 0, sizeof(dp));

        for (int i = 0; i <= k; ++i) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= k; ++j) {
                // 卖出时作为一次交易结束
                // 第一次交易dp[i][0][1] = dp[i - 1][0][0] - prices[i];
                // 第二次交易dp[i][1][1] = dp[i - 1][1][0] - prices[i]; dp[i][1][0] = dp[i - 1][0][1] + prices[i];
                // 第k次买入: dp[i][k - 1][1] = dp[i - 1][k - 1][0] - prices[i];
                // 第k次卖出: dp[i][k][0] = dp[i - 1][k - 1][1] + prices[i];
                dp[i][j - 1][1] = max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0] - prices[i]);
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][1] + prices[i]);
            }
        }

        return dp[n - 1][k][0];
        /* 空间优化版
        int dp[k + 1][2];

        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= k; i++) {
            dp[i][0] = 0;
            dp[i][1] = -prices[0];
        }

        for (int i = 1; i < n; ++i) {
            for (int j = k; j > 0; --j) {
                dp[j - 1][1] = max(dp[j - 1][1], dp[j - 1][0] - prices[i]);
                dp[j][0] = max(dp[j][0], dp[j - 1][1] + prices[i]);
            }
        }

        return dp[k][0];
        */
    }
};

// k = +infinity with cooldown
class statusMaxProfitWithCooldown {
public:
    int maxProfitWithCooldown(vector<int>& prices) {
        int n = prices.size();
        if (n <= 1)
            return 0;
        int dp[n][2];
        memset(dp, 0, sizeof(dp));
        dp[0][1] = -prices[0];
        dp[0][0] = 0;
        dp[1][1] = max(-prices[0], -prices[1]);
        dp[1][0] = max(0, prices[1] - prices[0]);

        for (int i = 2; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
        }

        return dp[n - 1][0];

        /* 空间优化版
        int n = prices.size();
        int dp_i0 = 0, dp_i1 = -prices[0];
        int dp_pre_0 = 0;

        for (int i = 0; i < n; i++) {
            int t = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + prices[i]);
            dp_i1 = max(dp_i1, dp_pre_0 - prices[i]);
            dp_pre_0 = t;
        }

        return dp_i0;
        */
    }
};

// k = +infinity with fee
class statusMaxProfitWithFee {
public:
    int maxProfitWithFee(vector<int>& prices, int fee) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        return dp[n - 1][0];

        /* 空间优化版
        int n = prices.size();
        int dp_i0 = 0, dp_i1 = -prices[0];

        for (int i = 1; i < n; ++i) {
            int t = dp_i0;
            dp_i0 = max(dp_i0, dp_i1 + prices[i] - fee);
            dp_i1 = max(dp_i1, t - prices[i]);
        }

        return dp_i0;
        */
    }
};